1. Field of the Invention
The field of the invention relates to data storage for data processing apparatus and in particular to multi-level hierarchical data storage.
2. Description of the Prior Art
Multi-level cache hierarchies are known in which lower level caches are provided close to a processor to provide easy access to data or instructions. These caches are quick to access, but expensive to implement, and thus, only store a limited subset of the data that may be needed. Additional data may be stored in higher level caches, which are larger and cheaper to implement than the lower level caches, but require more time to access, above this there may be other hierarchical levels of storage such as memory. These can store a very large amount of data but take significantly longer to access.
A drawback with multi-level hierarchies of data storage is that a data item may be stored in more than one level of store at any time, and thus, coherency needs to be maintained between the different stores to ensure that if one copy of the data item is overwritten in one store, the storage system knows which of the multiple stored values is the current value.
Inclusive caches are known and are described in “The Cache Memory Book” by Jim Handy pages 132 to 135, Academic Press second edition, these store duplicate copies of items stored in a lower level cache in a higher level cache. These inclusive caches have generally not been implemented in processors as cache storage space is expensive and thus, there is a prejudice against automatically storing duplicate values.
Another drawback with multi-level hierarchical stores is that when allocating an entry in a higher level store, a lower level store may need to be snooped to determine if the entry is present in the lower level store and this is time consuming.
It would be desirable to provide multi-level hierarchical data stores in which lines can be allocated efficiently.